﻿// 2584. 分割数组使乘积互质.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;

/*
https://leetcode.cn/problems/split-the-array-to-make-coprime-products/description/

给你一个长度为 n 的整数数组 nums ，下标从 0 开始。
如果在下标 i 处 分割 数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割 有效 。
例如，如果 nums = [2, 3, 3] ，那么在下标 i = 0 处的分割有效，因为 2 和 9 互质，而在下标 i = 1 处的分割无效，因为 6 和 3 不互质。
在下标 i = 2 处的分割也无效，因为 i == n - 1 。
返回可以有效分割数组的最小下标 i ，如果不存在有效分割，则返回 -1 。
当且仅当 gcd(val1, val2) == 1 成立时，val1 和 val2 这两个值才是互质的，其中 gcd(val1, val2) 表示 val1 和 val2 的最大公约数。



示例 1：
输入：nums = [4,7,8,15,3,5]
输出：2
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2。

示例 2：
输入：nums = [4,7,15,8,3,5]
输出：-1
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
不存在有效分割。

提示：
n == nums.length
1 <= n <= 104
1 <= nums[i] <= 106
*/

//tle 待优化

class Solution {
public:
    int findValidSplit(vector<int>& nums) {
        if (nums.size() == 1) return -1;
        if (nums[0] == 1) return 0;
        unordered_map<int, int> mm;
        for (int i = 0; i < nums.size(); i++) {
            int val = nums[i];
            for (int j = 2; j <= val / j; j++) {
                while (val % j == 0) {
                    val /= j;
                    mm[j] = max(mm[j], i);
                }
            }
            if (val != 1) mm[val] = max(mm[val], i);
        }
        int right = -1;
        for (int i = 0; i < nums.size(); i++) {
            int val = nums[i];
            for (int j = 2; j <= val / j; j++) {
                while (val % j == 0) {
                    val /= j;
                    right = max(right, mm[j]);
                }
            }
            if (val != 1) { right = max(right, mm[val]); }

            if (right <= i && right != nums.size()-1) return right;
        }

   
        return -1;
    }
};

//4,7,8,15,3,5
//4,7,15,8,3,5

int main()
{
    Solution s;
    vector<int> v{ 4,7,15,8,3,5 };
    cout << s.findValidSplit(v);
	return 0;
}

 